/*
  实验4 队列操作
*/
  #include <stdio.h>
  #include <stdlib.h>
  #define TRUE 1
  #define FALSE 0
  #define NULL 0
  #define OK         1
  #define ERROR      0
  #define INFEASIBLE -1
  #define OVERFLOW   -2
 //Status 是函数的类型，其值是函数结果状态代码
  typedef int Status;
  typedef int ElemType;
  typedef int QElemType;
 
  //----  定义顺序队列的存储结构
  #define MAXQSIZE 12  //顺序循环队列的最大长度
  typedef  struct
  { 
	QElemType  *base; //存放队列元素的数组空间
	int front;  //头指针，若队列不空，则指向队列头元素
	int rear;    //尾指针，若队列不空，则指向队列尾元素的下一个存储单元
   }SqQueue;

 //初始化队列 
  Status InitQueue(SqQueue &Q) 
{
     Q.base =new QElemType[MAXQSIZE];
      if(!Q.base) exit(OVERFLOW);
     Q.front = 0;  //队头指针赋初值
     Q.rear = 0;    //队尾指针赋初值	 
      return OK;
 }//InitQueue

Status CreateQueue(SqQueue &Q,QElemType A[],int n) //初始化队列
//初始条件：A[]中存在队列的n个数据元素。操作结果：构造1个含有n个数据元素的队列Q。
{
	Q.base =new QElemType[n]; //开辟n个元素的队列空间，并返其首地址
	Q.front =0;
	Q.rear =0;
	for(int i=1;i<=n;++i) 
	{
		Q.base[Q.rear]=A[i-1];     //A的各个元素依次写入Q队列。
		Q.rear++;      //队尾指针加1
        Q.rear=Q.rear%MAXQSIZE;
	}	
	return OK;
}//CreateQueue

//入队
Status EnQueue(SqQueue &Q, QElemType  e)
{ //插入元素e为Q的新的队尾元素
  if  ((Q.rear+1)%MAXQSIZE==Q.front)   //判断队列是否满
  {
      printf(" SqQueue FULL ERROR !\n");
	  return ERROR;    //队列满返回ERROR，即返回 0
  }
 Q.base[Q.rear]=e; //元素入队
 Q.rear++; //队尾指针加1
 Q.rear = Q.rear%MAXQSIZE;
  return OK;
}// EnQueue 

//出队
Status DeQueue(SqQueue &Q, QElemType &e){
//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK;否则返回ERROR
  if(Q.front==Q.rear)     //判断队列是否空
       return ERROR;     //队列空返回，即返回 0
  e=Q.base[Q.front];    //将队头元素赋给e
 Q.front++;  //队头指针向后移动(队头指针加1) ,队头元素被删除 
 Q.front=Q.front%MAXQSIZE;
  return OK;
}// DeQueue

//判队空
Status QueueEmpty(SqQueue Q) {  //Status QueueEmpty(SqQueue &Q)  ??
    return Q.front==Q.rear;    //判断队列是否空
}

//判队满
Status QueueFull ( SqQueue Q ) {   //Status QueueFull ( SqQueue &Q )  ??
    return (Q.rear+1)%MAXQSIZE==Q.front;   //返回队列是否满，队满返回1，否则返回0
}

//求队长    
int QueueLength (SqQueue &Q) {
//返回Q的元素个数,即队列的长度
 return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; //返回队列中的元素个数
}//QueueFull 

//取循环队列队头元素
QElemType GetHead(SqQueue Q){
//返回队头元素,不修改队头指针
  if(Q.rear!=Q.front)
       return   Q.base[Q.front];
  return ERROR;
}// GetHead


// 遍历队列 
void Display(SqQueue Q)
 {
	  SqQueue r;
	  r.front =Q.front;	  
	  if( Q.front==Q.rear )
	  {
		printf(" SqQueue empty !\n");
		return;
	  }
      else 
	  {
         		printf(" in order SqQueue :");
		while (Q.rear!=r.front)  //当没有到达队尾时
         		{  
            		 	printf("%d <- ",Q.base[r.front]);  
			r.rear= r.front;
			r.front=(r.front+1)%MAXQSIZE;  //队头指针指向下一个元素
	                }
         		printf("\n");		
		printf(" The position of tail: rear=%d\n",Q.base[r.rear]);		 
        		 printf(" The position of head: front=%d\n",Q.base[Q.front]);
    	 }

  }//Display

//  #include "SqQueue.h"
  /* 主函数 */
  int main() 
  {
     int x,y,z,e,a[20],n,select;
	 SqQueue head;
     //head=(SqQueue *)malloc(sizeof(SqQueue));
     do {
      printf("\n============= 实验4 队列的操作 =============\n ");
      printf(" 23计算机科学与技术专升本3  23230810047  李皓天\n ");            //请填写相应的个人信息
      printf(" 测试数据：按要求构成\n ");    //请填写具体测试数据
    printf("=========== 实验报告 2023-11-14==========\n\n");   //这部分信息应与实验日期对应
       printf("\n first be used  must be initiated ! \n");
       printf("please choose(0--7): \n");
       printf("================= menu ================\n\n");
       printf("         1    Initiate SqQueue  \n");
       printf("         2    Create SqQueue \n");
       printf("         3    Append SqQueue element  \n");
       printf("         4    Delete SqQueue element  \n");
       printf("         5    Is Empty SqQueue ? \n");
       printf("         6    Gethead element  \n");
       printf("         7    Display SqQueue  \n");
	   printf("         8    Is Full SqQueue  \n");
       printf("         0    Exit  \n");
       printf("\n=======================================\n");
       scanf("%d",&select);
       switch(select)
       {
	 case 1: {
		InitQueue(head);
                  	printf(" Sqqueue have been Initiated !\n");
		Display(head);
                  	break;
                  	}
	 case 2: {
		  //printf(" Input SqQueue Length : ");  //输入学号时用
		  //scanf("%d",&n);                      //输入学号的长度
		  n=11;                               //请修改此句，n取值为学号的长度
          int a[11]={2,3,2,3,0,8,1,0,0,4,7};     //请修改此句为scanf("%d",&a[i-1]); 将个人学号依次赋给a[i]
		  CreateQueue(head,a,n);
            		  printf(" SqQueue have been created !\n");
                 	  Display(head);
                 	  break;
                  	 }
	 case 3: {
	                  printf(" Input SqQueue value:\n");
                  	  scanf("%d",&x);
                 	  EnQueue(head,x);
                	  Display(head);
               		  break;
                	  }
	 case 4: {
        printf("input value:");
        scanf("%d",&e);
		  z=DeQueue(head,e);
	          	  printf(" SqQueue head element %d be deleted! \n",z);
                 	  Display(head);
                  	  break;
                	  }
	 case 5: {
		  if(QueueEmpty(head)) printf(" Sqqueue is empty !\n");
		  else  printf(" SqQueue is not empty !\n");
                  	  Display(head);
                  	  break;
                  	  }
	 case 6: {
                 	  y=GetHead(head);
		  printf(" SqQueue head element : %d \n",y);
                  	  Display(head);
                  	  break;
                 	  }
	 case 7: {
                 	  Display(head);
                 	  break;
                  	  }
	 case 8: {
                  	  if(QueueFull(head)) 
	 	     printf(" Sqqueue is full !\n");
		     // Display(head);
		   else  
		     printf(" SqQueue is not full !\n");
		  Display(head);
                  	  break;
                  	  }
	 case 0: exit(0);
      }
    } while(select<=8);
    return 0;
 }
